package com.zjsru.plan2024.oneday;

import com.zjsru.common.TreeNode;

import java.util.HashSet;
import java.util.Set;

/**
 * 1261. 在受污染的二叉树中查找元素
 * root.val == 0
 * 如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
 * 如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2
 * 现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。
 * FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
 * bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。
 * @Author: cookLee
 * @Date: 2024-03-12
 */
public class FindElements {

    /**
     * 主
     * \
     * 输入：
     * ["FindElements","find","find"]
     * [[[-1,null,-1]],[1],[2]]
     * 输出：
     * [null,false,true]
     * 解释：
     * FindElements findElements = new FindElements([-1,null,-1]);
     * findElements.find(1); // return False
     * findElements.find(2); // return True
     * \
     * 输入：
     * ["FindElements","find","find","find"]
     * [[[-1,-1,-1,-1,-1]],[1],[3],[5]]
     * 输出：
     * [null,true,true,false]
     * 解释：
     * FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
     * findElements.find(1); // return True
     * findElements.find(3); // return True
     * findElements.find(5); // return False
     * \
     * 输入：
     * ["FindElements","find","find","find","find"]
     * [[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
     * 输出：
     * [null,true,false,false,true]
     * 解释：
     * FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
     * findElements.find(2); // return True
     * findElements.find(3); // return False
     * findElements.find(4); // return False
     * findElements.find(5); // return True
     * \
     * @param args args
     */
    public static void main(String[] args) {
        FindElements findElements = new FindElements();
        TreeNode root = new TreeNode(-1,null,new TreeNode(-1));
        findElements.findElements(root);
    }

    /**
     * 树节点集
     */
    private Set<Integer> valSet;

    /**
     * 查找元素
     *
     * @param root 根
     */
    private void findElements(TreeNode root) {
        this.valSet = new HashSet<>();
        this.dfs(root,0);
    }

    /**
     * 深度优先搜索助手类
     *
     * @param node 节点
     * @param val    我
     */
    private void dfs(TreeNode node, int val) {
        if (node == null) {
            return;
        }
        node.val = val;
        valSet.add(val);
        this.dfs(node.left, val * 2 + 1);
        this.dfs(node.right, val * 2 + 2);
    }

    /**
     * 查找
     *
     * @param target 目标
     * @return boolean
     */
    private boolean find(int target) {
        return valSet.contains(target);
    }


}
